﻿#include <iostream>
#include <stack>

using namespace std;

// 获取栈底元素
static int getBottom(stack<int>& numStack)
{
    if (numStack.size() == 1)
    {
        int top = numStack.top();
        numStack.pop();
        return top;
    }

    int top = numStack.top();
    numStack.pop();
    int bottom = getBottom(numStack);
    numStack.push(top);
    return bottom;
}

static void reverse(stack<int>& numStack)
{
    if (numStack.empty())
    {
        return;
    }

    int bottom = getBottom(numStack);
    reverse(numStack);
    numStack.push(bottom);
}

// 给你一个栈，请你逆序这个栈，不能申请额外的数据结构，只能使用递归函数。
int main_ReverseStack()
{
    stack<int> numStack;
    numStack.push(6);
    numStack.push(5);
    numStack.push(4);
    numStack.push(3);
    numStack.push(2);
    numStack.push(1);

    reverse(numStack);
    return 0;
}